package dac.sort.core;

/**
 * 合并排序
 * 期望时间T(n)=θ(nlgn)
 *
 */
public class MergeSort implements Sort{

	/**
	 * 排序方法主体
	 * @param array 待排序数组
	 * @param sortType 排序策略
	 */
	public int[] sort(int[] array, int sortType) {
		int len = array.length;
		
		/**
		 * 将数组分为两组：(0~n/2) 和 (n/2~n)
		 */
		int[] array1 = new int[len/2];
		int[] array2 = new int[len-len/2];
		for (int i = 0; i < len; i++) {
			if(i < len/2)
				array1[i] = array[i];
			else
				array2[i-len/2] = array[i];
		}
		/**对第一组数组进行排序，除非该数组只有一个元素*/
		int[] sortedArray1 = array1.length > 1 ? sort(array1, sortType) : array1;
		/**对第二组数组进行排序，除非该数组只有一个元素*/
		int[] sortedArray2 = array2.length > 1 ? sort(array2, sortType) : array2;
		
		int index1 = 0;
		int index2 = 0;
		
		int[] sortedArray = new int[len];
		/**把两个排好序的数组进行合并*/
		for (int i = 0; i < len; i++) {
			/**两个数组都在索引中，升序取当前索引小的那个元素，降序取当前索引大的那个元素*/
			if (index1 < sortedArray1.length && index2 < sortedArray2.length) {
				if (sortedArray1[index1] > sortedArray2[index2]) {
					if(sortType == SortType.ASC){
						sortedArray[i] = sortedArray2[index2];
						index2++;
					} else {
						sortedArray[i] = sortedArray1[index1];
						index1++;
					}
				} else {
					if(sortType == SortType.ASC){
						sortedArray[i] = sortedArray1[index1];
						index1++;
					} else {
						sortedArray[i] = sortedArray2[index2];
						index2++;
					}
				}
			}
			/**数组1脱离索引后，直接取数组2的元素到结果数组中*/
			else if (index1 == sortedArray1.length) {
				sortedArray[i] = sortedArray2[index2];
				index2 ++;
			}
			/**数组2脱离索引后，直接取数组1的元素到结果数组中*/
			else if (index2 == sortedArray2.length){
				sortedArray[i] = sortedArray1[index1];
				index1 ++;
			}
		}
		return sortedArray;
	}

}
